The present invention relates to a method and apparatus for evaluating a scale factor and a rotation angle in image processing.
In many optically automated applications, there is a need for the evaluation of the rotation angle or scale of an object. For example, if an electronic chip has to be soldered on a printed circuit board, the exact orientation of the object has to be known to ensure a good fit between the pins of the chip and the connectors of the printed-circuit board.
In other applications, it is required to evaluate the distance of an object from a camera, such as for a robot to go pick up an object or, within a pattern recognition system, to compare the object with reference templates at the correct scale factor. The distance between the object and the camera is directly proportional to the scale of the object observed by the camera. Knowing the scale of an object compared to a reference is equivalent to knowing the distance. In both cases this information is useful for further processing, such as in the case of pattern recognition, target tracking and other applications.
A fair amount of research has been done in this field. Among others, U.S. Pat. No. 5,067,019 to Juday et al. entitled xe2x80x9cProgrammable remapper for image processingxe2x80x9d describes an image processing system for realising image pre-processing for maculopathy. It is also suggested that the pre-processor described in this patent could also be useful for optical correlators. However, the different functions described are the usual log-polar, ring-wedge, log-log mathematical operations. The problem with these functions is that they give rise to the problem of image centering. Because these techniques give different object representations for different centers of expansion, the object has to be centered conveniently before the recognition can be properly effected.
Most of the other known techniques are derived from the field of pattern recognition where an object has to be recognised with invariance to scale, rotation and size. One of these techniques is based on the expansion of the object in mathematical components (see, for example, Y. N. Hsu and H. H. Arsenault, xe2x80x9cPattern Discrimination by Multiple Circular Harmonic Componentsxe2x80x9d, Appl. Opt., 23, 841, (1984)). Other techniques are based on geometrical or mathematical transformation of an object, such as the techniques described in Y. Sheng, C. Lejeune, H. H. Arsenault, xe2x80x9cFrequency-domain Fourier-Mellin descriptors for invariant pattern recognitionxe2x80x9d, Optical Engineering, 27, 5, 354, (1988), and D. Casasent, S-F X., A. J. Lee, J.-Z Song, xe2x80x9cReal-time deformation invariant optical pattern recognition using coordinate transformationsxe2x80x9d, Applied Optics, 26, 5, 1987.
Invariant moments are also used for these kinds of operations, and in this case, the moments of inertia are computed according to a center of expansion. This technique is described in Q. Zhan, T. Minemoto, xe2x80x9cMoment invariants for pattern recognition under translation, rotation, and changes of size and brightnessxe2x80x9d, Journal of Modern optics, 40, 11, 2267, 1993.
These methods suffer from different problems that can be itemized as follows:
The gain of an invariance, for instance rotation, will be accompanied by a loss of the robustness for another invariance, for example scale robustness;
The gain of an invariance is often accompanied by a loss of information on the object;
The information on the rotation angle or scale factor is lost with the adjunction of invariance, so one is able to locate an object but is not easily able to identify its rotation angle or scale factor;
The evaluation of the angle of rotation or scale factor thus requires display of multiple filters, increasing the processing time. As such, the time required to evaluate 1024 rotation angle or scale factors is 1024 times greater than the one required for one rotation angle and one scale factor.
Most of these methods rely on finding an appropriate center of expansion of an object, which itself requires considerable computations; and
When a technique requires a center of expansion, it is then intrinsically not able to operate in the presence of multiple objects in the input plane.
It is an object of the invention to provide a method and apparatus for performing scale factor and rotation evaluation in an image processing system, which reduces the amount of computations required to obtain useful results. Also, the invention is concerned with a method and apparatus which does not require object centering prior to performing the analysis, and which does not require complex mathematical expansion of the object under analysis. Other objects will become apparent hereinafter.
In accordance with the invention, this object is achieved with:
a method for evaluating a scale factor and a rotation angle in image processing, comprising the steps of:
(a) providing an input image;
(b) reducing the input image to provide a smaller image;
(c) scaling the smaller image according to a plurality of factors to produce a plurality of scaled images;
(d) rotating the smaller image according to a plurality of factors to produce a plurality of rotated images;
(e) placing the scaled images and the rotated images into a mosaic arranged by scale and rotation;
(f) providing a reference template;
(g) correlating said reference template with said mosaic of scaled and rotated images; and
(h) providing a scale factor and a rotation angle based on the position in the mosaic of the highest correlation value between the reference template and the scaled and rotated images;
a method for evaluating a scale factor and a rotation angle in image processing, comprising the steps of:
(a) providing an input image;
(b) reducing the input image to provide a smaller image;
(c) providing a reference template;
(d) scaling the reference template according to a plurality of factors to produce a plurality of scaled images;
(e) rotating the reference template according to a plurality of factors to produce a plurality of rotated images;
(f) placing the scaled images and the rotated images into a mosaic arranged by scale and rotation;
(g) correlating said smaller image with said mosaic of scaled and rotated images; and
(h) providing a scale factor and a rotation angle based on the position in the mosaic of the highest correlation value between the smaller image and the scaled and rotated images.
Another aspect of the invention concerns a system for evaluating a scale factor and a rotation angle in image processing, comprising:
(a) input means for receiving an input image;
(b) means for reducing the input image to provide a smaller image;
(c) means for scaling the smaller image according to a plurality of factors to produce a plurality of scaled images;
(d) means for rotating the smaller image according to a plurality of factors to produce a plurality of rotated images;
(e) means for receiving and placing the scaled images and the rotated images into a mosaic arranged by scale and rotation;
(f) means for providing at least one reference template;
(g) means for correlating each of said at least one reference template with said mosaic of scaled and rotated images; and
(h) means for providing a scale factor and a rotation angle based on the position in the mosaic of the highest correlation value between each of the reference templates and the scaled and rotated images;
Alternatively, the present invention concerns a system for evaluating a scale factor and a rotation angle in image processing, comprising:
(a) input means for receiving an input image;
(b) means for reducing the input image to provide a smaller image;
(c) means for providing at least one reference template;
(d) means for scaling each of the at least one reference template according to a plurality of factors to produce a plurality of scaled images;
(e) means for rotating each of the at least one reference template according to a plurality of factors to produce a plurality of rotated images;
(f) means for placing the scaled images and the rotated images into a mosaic arranged by scale and rotation for each of the reference template;
(g) means for correlating said smaller image with each of said mosaic of scaled and rotated images; and
(h) means for providing a scale factor and a rotation angle based on the position in the mosaic of the highest correlation value between the smaller image and the scaled and rotated images;
Finally, a method for evaluating a scale factor and a rotation angle in image processing is described, comprising the steps of:
(a) providing an input image;
(b) scaling the image according to a plurality of factors to produce a plurality of scaled images;
(c) rotating the image according to a plurality of factors to produce a plurality of rotated images;
(d) placing the scaled images and the rotated images into a mosaic arranged by scale and rotation;
(e) providing a reference template;
(f) correlating said reference template with said mosaic of scaled and rotated images; and
(g) providing a scale factor and a rotation angle based on the position in the mosaic of the highest correlation value between the reference template and the scaled and rotated images.